package dp;

/**
 * 最长公共子串，（子串要求元素之间是连续的）
 * 这里还是用数组来表示原始字符串
 *
 * @author zj
 */
public class LongestCommonSubstring {
    public static void main(String[] args) {
        int arr1[] = {1, 3, 5, 2, 7, 6, 7, 9};
        int arr2[] = {2, 3, 5, 6, 7, 9};
        System.out.println(solution(arr1, arr2));
    }

    public static int solution(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null || arr1.length == 0
                || arr2.length == 0) {
            return 0;
        }
        int tmp[][] = new int[arr1.length + 1][arr2.length + 1];
        //边界条件
        for (int i = 0; i <= arr1.length; i++) {
            tmp[i][0] = 0;
        }
        for (int j = 0; j <= arr2.length; j++) {
            tmp[0][j] = 0;
        }
        int max = 0;
        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                if (arr1[i - 1] == arr2[j - 1]) {
                    tmp[i][j] = tmp[i - 1][j - 1] + 1;
                } else {
                    //这里是和求最长公共子序列的唯一区别
                    tmp[i][j] = 0;
                }
                System.out.println("tmp[" + i + "][" + j + "] = " + tmp[i][j]);
                max = Math.max(max, tmp[i][j]);
            }
        }
        return max;
    }
}
